package com.sam.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * 求出无序数组的最大前m个数,并按从小到大排序
 *
 * 分-治
 * 1. 找出前M个，放在右侧（类似快速排序，只需要排一半）
 * 2. 对前M个进行排序
 *
 * Created by samwang on 2017/12/17.
 */
public class MaxMFromArray {
    public static void main(String[] args) {
//        int[] a = {2, 5, 1, 35, 9,7, 8, 6, 4};
//        int[] a = {2, 1, 3, 45, 222, 7, 19, 35};
        int[] a =new int[20];
        Random random = new Random();
        for (int i = 0; i < 20; i++) {
            a[i] = random.nextInt(1000);

        }
        int m = 4;
        arrangeRight(a, 0, a.length-1, m);
        quickSort(a, a.length - m - 1, a.length - 1);
        System.out.println(Arrays.toString(Arrays.copyOfRange(a, a.length - m , a.length )));
        System.out.println(Arrays.toString(a));

       // quickSort(a, 0, a.length - 1);
        //System.out.println(Arrays.toString(a));

    }

    /**
     * a[s]-a[e]将前m大的数移到右边
     */
    public static void arrangeRight(int[] a, int s, int e, int m) {
        if (s >= e) {
            return;
        }
        int k = commonQuickSort(a, s, e);
        int kToEnd = e - k + 1;
        if ( kToEnd > m) {//右侧数字多于m，则在右侧排前m
            arrangeRight(a, k + 1, e, m);
        } else if (kToEnd < m) {//右侧数字小于m,则在左侧找出缺少的部分
            arrangeRight(a, s, k - 1, m - kToEnd);
        }
        //排序完成

    }

    public static void quickSort(int[] a, int start, int end) {
        if (start >= end) {
            return;
        }
        int k = commonQuickSort(a, start, end);
        quickSort(a, start, k - 1);
        quickSort(a, k+1, end);
    }

    /**
     * 快速排序
     * @param a
     * @param start
     * @param end
     */
    public static int commonQuickSort(int[] a, int start, int end) {
        if (start >= end) {
            return start;
        }
        int k = a[start];
        int i = start;
        int j = end;

        while (i != j) {
            while (i < j && a[j] >= k) {
                j--;
            }

            if (i == j) {
                break;
            }
            //方法1 直接交换-----
//                swipe(a, i, j);
            //方法1-----

            //方法2 -----
            a[i] = a[j];
            i++;
            //方法2 -----


            while (i < j && a[i] <= k) {
                i++;
            }
            if (i == j) {
                break;
            }

            //方法1 直接交换-----
//                swipe(a, i, j);
            //方法1-----

            //方法2 -----
            a[j] = a[i];
            j--;
            //方法2 -----
        }
        //方法2 -----
        a[i] = k;//i==j此时
        //方法2 -----

       return i;


    }

    public static void swipe(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }




}
